// 13006. 不同岛屿的数量 - 搜索
#include <set>

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

void dfs(vector<vector<int>>& matrix, int x0, int y0, int x, int y, vector<vector<int>>& path) {
    path.push_back({x-x0, y-y0});   //路径记录相对坐标
    int m = matrix.size(), n=matrix[0].size();
    int k, nx, ny;
    for(k = 0; k < 4; ++k)
    {
        nx = x + dx[k];
        ny = y + dy[k];
        if(nx>=0 && nx<m && ny>=0 && ny<n && matrix[nx][ny]==1)
        {
            matrix[nx][ny] = 0;   //访问过
            dfs(matrix, x0, y0, nx, ny, path);
        }
    }
}

int solve(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty())  return 0;
    set<vector<vector<int>>> paths; // 每个岛屿存储一个搜索路径，利用set去重
    int m = matrix.size(), n=matrix[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1)
            {
                vector<vector<int>> path;
                matrix[i][j] = 0;   //访问过
                dfs(matrix, i, j, i, j, path);
                paths.insert(path);
            }
        }
    }
    return paths.size();
}